package J.算法.动态规划;

/**
 * 比较特殊的动态规划
 *  并不能从一端开始规划 而是两端往中间规划
 */
public class _5最长回文子串 {
    //中间字串 动态规划

    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new  boolean[n][n];

        String res = "";
        //用l来循环字串的长度 l+1代表长度
        for (int l = 0;l<n;l++){
            for (int i = 0; i < n-1; i++) {
                int j = i+1;
                if (l == 0){
                    dp[i][j] = true;
                }else if (l == 1){
                    dp[i][j] = (s.charAt(i)==s.charAt(j));
                }else {
                    dp[i][j] = (s.charAt(i)==s.charAt(j)) && dp[i+1][j-1];
                }

                if (dp[i][j] && l+1 > res.length()){
                    res = s.substring(i,i+l+1);
                }

            }
        }

        return res;




    }

}
